Classic pathfinding algorithms like Dijkstra's Algorithm and A* are used to generate travel routes in applications such as video games, mobile robotics, and architectural design. Despite the popularity of these algorithms, the paths they produce rarely go straight. In this article, you'll learn how to compute highly direct paths using a counting technique inspired by Pascal's Triangle. It's an idea my colleagues and I developed and recently published in the Journal of Artificial Intelligence Research [1]. With the simple step of counting paths, you can overcome a long-standing problem with traditional pathfinding.

Counting the number of shortest paths on a grid is a simple procedure with close ties to Pascal's triangle. We show how path counting can be used to select relatively direct grid paths for AI-related applications involving navigation through spatial environments. Typical implementations of Dijkstra's algorithm and A* prioritize grid moves in an arbitrary manner, producing paths which stray conspicuously far from line-of-sight trajectories. We find that by counting the number of paths which traverse each vertex, then selecting the vertices with the highest counts, one obtains a path that is reasonably direct in practice and can be improved by refining the grid resolution. Central Dijkstra and Central A* are introduced as the basic methods for computing these central grid paths. Theoretical analysis reveals that the proposed grid-based navigation approach is related to an existing grid-based visibility approach, and establishes that central grid paths converge on clear sightlines as the grid spacing approaches zero. A more general property, that central paths converge on direct paths, is formulated as a conjecture.

This path, however, is typically not a shortest path in the continuous terrain. In this overview article, we discuss a path-planning methodology for quickly finding paths in continuous terrain that are typically shorter than shortest grid paths. Anyangle path-planning algorithms are variants of the heuristic path-planning algorithm A* that find short paths by propagating information along grid edges (like A*, to be fast) without constraining the resulting paths to grid edges (unlike A*, to find short paths). In robotics and video games, (continuous) terrain is often discretized into grids with blocked and unblocked grid cells and from there into grid graphs (Tozour 2004; Rabin 2000; Chrpa and Komenda 2011; Björnsson et al. 2003; Nash 2012). Our objective is to find short unblocked paths from given start vertices to given goal vertices.

In robotics and video games, one often discretizes continuous terrain into a grid with blocked and unblocked grid cells and then uses path-planning algorithms to find a shortest path on the resulting grid graph. This path, however, is typically not a shortest path in the continuous terrain. In this overview article, we discuss a path-planning methodology for quickly finding paths in continuous terrain that are typically shorter than shortest grid paths. Any-angle path-planning algorithms are variants of the heuristic path-planning algorithm A* that find short paths by propagating information along grid edges (like A*, to be fast) without constraining the resulting paths to grid edges (unlike A*, to find short paths).